package dfs;

import java.util.ArrayList;
import java.util.List;

//n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
//皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
public class n皇后问题 {
    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(8);
        System.out.println(lists.toString());
        System.out.println(lists.size());
    }
    public static List<List<String>> solveNQueens(int n) {
        char[][] chars = new char[n][n];
        List<List<String>> lists = new ArrayList<>();
        //初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                chars[i][j]='.';
            }
        }
        res(lists,chars,0);
        return lists;
    }

    private static void res(List<List<String>> lists, char[][] chars, int row) {
        if (row==chars.length) {
            lists.add(constract(chars));
            return;
        }
        for (int col = 0; col <chars[0].length ; col++) {
            if (vaild(chars,row,col)) {
                chars[row][col] = 'Q';
                res(lists,chars,row+1);
                chars[row][col]='.';
            }
        }
    }
    //将字符二维数组转化为List类型
    private static List<String> constract(char[][] chars) {
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            list.add(new String(chars[i]));
        }
        return list;
    }
    private static boolean vaild(char[][] chars, int row, int col) {
        //只用判断当前即可
        //判断列是否满足条件
        for (int i = 0; i< row; i++) {
            if (chars[i][col]=='Q')
                return false;
        }
        //判断右上方是否满足条件
        for(int i=row-1,j=col+1; i>=0 && j<chars.length;i--,j++){
            if (chars[i][j]=='Q')
                return false;
        }
        //判断左上方是否满足条件
        for (int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if (chars[i][j]=='Q')
                return false;
        }
        return true;
    }
}
